A Tutorial on Network Embeddings

发表于

介绍

  原文地址

  NE（network embedding）的中心思想是找到一种映射函数，可以将网络中的每一个节点转换为一个低维潜在表示。这些表示可以作为特征，用于在图上的一般任务，如分类，聚类，链路预测和可视化。

Alt text

  目标：

  1. 适应性。

    • 真正的网络在不断演化。不应要求重复学习过程。

  2. 可扩展。

    • 真正的网络通常很巨大，因此网络嵌入算法应该在短时间内处理大规模的网络。

  3. 社区感知。

    • 潜在表示之间的距离应该用以表示对应的节点之间的相似性度量。

  4. 低维。

    • 当标注数据稀缺时，低维模型泛化的更好，并能加速收敛和推理。

  5. 连续性。

    • 要求在连续空间内，潜在表示能建模部分社区成员关系。除了提供社区成员关系的细微视角外，连续的表示在社区间具有平滑的决策边界，令分类更鲁棒。

    此文包含：

    • 网络嵌入的概述
    • 无监督网络嵌入方法在无特征同质网络上的应用
    • 在特征网络和部分标注网络上的嵌入方法
    • 讨论异质网络嵌入算法

网络嵌入的简短历史

传统意义的网络嵌入

  传统意义上，图嵌入被视为降维。

  1. PCA
  2. 多维缩放（MDS）
    • 将 M 的每一行投影到 k 维向量，同时在 k 维空间中保留 不同对象在原始特征矩阵 M 中的距离。
  3. Isomap
    • Isomap是 MDS 的扩展，通过将每个节点与特定距离内的节点连接构造邻域图，在邻域图上使用 MDS ，以保持非线性流形的整体结构
  4. 局部线性嵌入（LLE）
    • 仅压榨数据点的局部邻域，不试图估计遥远数据点之间的距离。LLE 假设输入数据本质上是从某种潜在流行上采样得到的，一个数据点可以被重建为它邻居们的线性组合。

  方法1，2只能够捕捉线性结构信息，不能发现输入数据之间的非线性。通常来说，以上方法能在小网络上有很好的表现。然而，这些方法的时间复杂度至少是二次，无法在大规模网络上运行。

深度学习时代

  DeepWalk是被提出的第一个使用深度学习方法的网络嵌入方法。DeepWalk将节点当作单词，生成短的随机行走作为句子，弥合了网络嵌入和词嵌入之间的差距。然后，神经语言模型如 Skip-gram 可以应用在这些随机行走上获得网络嵌入。

DeepWalk范式的三个步骤：

  1. 选择一个和输入图关联的矩阵。
  2. 图采样，节点序列从选中的矩阵中采样得到。这一步是可选的。
  3. 从生成的序列（或是第一步选的矩阵）中学习节点嵌入。

DeepWalk范式是高度灵活的，其可从两方面被扩展：

  1. 被建模的图的复杂性可以被扩展。
  2. DeepWalk的两个关键成分的方法，即用于从潜在矩阵中采样序列和从采样的序列学习节点嵌入，都可被扩展。

DeepWalk

无监督网络嵌入

无向图嵌入

  DeepWalk 提出一种学习网络嵌入的两阶段算法。第一阶段是决定每一个节点得到上下文节点。通过在网络中生成截断的随机行走，上下文节点 v 可被定义为每一个随机行走序列中一个大小为 k 窗口内的节点。一旦上下文节点确定好了，第二步同 Skip-gram 模型一样：最大化预测上下文节点的似然概率来学习嵌入。

Algorithm 1

  许多后续的在图嵌入的工作都追随 DeepWalk 中提出的两阶段框架，在每个阶段各有不同。下表总结了一些网络嵌入方法，按照它们对上下文节点的定义和用于学习嵌入的方法分类。

Table 1

  • LINE

    • 为了更好的保存网络的结构信息，提出了一阶相似度和二阶相似度的概念，并在目标函数中结合了两者

    • 使用宽度优先策略来产生上下文节点，只有距离给定节点最多两跳的节点才被视为相邻节点

    • 使用 Skip-gram with Negative Sampling

  • Node2vc

    • 引入有偏向的随机游走，联合了 BFS 和 DFS 探索近邻
  • Walklets
    • 从$A^1,A^2,…,A^k$学习多尺度网络嵌入，由于计算$A^i$的时间复杂度至少是网络中节点数量的平方，Walklets 通过在短随机游走间跳过节点来近似$A^i$。
    • 从$A$的不同幂次来学习，在不同粒度捕捉网络的结构信息。
  • GraRep
    • 通过将图形邻接矩阵提升到不同的幂来利用不同尺度的节点共现信息，将奇异值分解（SVD）应用于邻接矩阵的幂以获得节点的低维表示
  • GraphAttention
    • 不是预先确定超参数来控制上下文节点分布，而是自动学习对图转换矩阵的幂集数的关注
    • 通过设置隐藏层，这些层里的节点能够注意其邻近节点的特征，我们能够（隐含地）为邻近的不同节点指定不同的权重，不需要进行成本高昂的矩阵运算（例如反演），也无需事先知道图的结构
  • SDNE
    • 通过深度自动编码器保持 2 跳邻居之间的接近度。它通过最小化它们的表示之间的欧几里德距离来进一步保持相邻节点之间的接近度。
    • 具有多层非线性函数，从而能够捕获到高度非线性的网络结构。然后使用一阶和二阶邻近关系来保持网络结构。二阶邻近关系被无监督学习用来捕获全局的网络结构，一阶邻近关系使用监督学习来保留网络的局部结构。
  • DNGR
    • 使用随机冲浪来捕捉图结构信息。
    • 将这些结构信息转换为一个 PPMI 矩阵，使用 层叠降噪自动编码器来嵌入节点。

有向图嵌入

  前一节介绍的在无向图上操作的方法可以通过使用有向随机行走作为训练数据，自然地泛化到有向图上。

  • HOPE
    • 是专门为有向图设计的图嵌入方法。
    • 是保存非对称传递图嵌入的通用框架，整合了一些流行的近似测量如 Katz index
    • 使用泛化的SVD来优化

边嵌入

  如链路预测这样的任务要求对图的边准确建模。一种为边$e = (u,v)$构建表示的无监督方式是在$\phi(u)$和$\phi(v)$上运用二元算子：

binary operator

在node2vec中，考虑了一些二元算子，如平均数，Hardmard product，L1距离和L2距离。然而，这些对称二元算子总是对边$(u,v)$和$(v,u)$赋予相同的值，忽略了边的方向。

figure 5

  为了缓和这个问题，Abu-El-Haija等人一种通过低秩对称投影的边表示学习方法。他们的方法由三部分组成。如Figure 5所示。

签名图嵌入

  签名图中每一条边都有一个权重$w \in \{1,-1\}$，具有权重1的边代表节点之间的积极连结，反之则为负面连结。

  • SiNE
    • 基于结构平衡理论，一个节点同敌人相比，于朋友更接近。SiNE通过最大化朋友的嵌入相似性和敌人的嵌入相似性之间的间距来保持这个性质。
    • 负连结很系数时，引入一个虚拟节点来保持这种性质。
  • SNE
    • 通过连个一个节点的上下文节点的表示来预测该节点的表示。

子图嵌入

  另一个研究分支是关于图的大规模成分的嵌入，如图的子结构或整个图。Yanardag 和 Vishwanathan提出深度图核，是一种建模图中子结构相似性的通用框架。两个图$\mathcal{G}$和$\mathcal{G}’$之间的核如下：

graph kernel

但这些表示不能揭示两个不同但相似子结构之间的相似性。也就是，即使两个图仅仅有一条边或是一个顶点不同，它们被视为完全是不同的。这种核定义导致了对角优势问题：一个图只能与它自己相似，而不能和其他图相似。为了克服这个问题，Yanardag 和 Vishwanathan提出了另一种核定义：

alternative graph kernel

为了构建$\mathcal{M}$，他们的算法首先生成图子结构的共现矩阵。然后使用Skip-gram模型在共现矩阵上训练过的子结构的潜在表示，使用其来计算$\mathcal{M}$。

使用元策略来改进网络嵌入

  至今用于网络嵌入的神经方法，都具有一些相同的弱点。首先，它们都是局部方法——受限于节点周围的结构。这种聚焦于局部结构的方法忽略了远距离的全局关系。其次，它们都依靠非收敛的优化目标，这往往使用随机梯度下降，而其会导致困在局部最小值。换句话说，这些方法学习的嵌入配置，可能会丢弃输入图的重要结构特征。

  HARP递归的合并原始图中的点和边，成功得到一系列具有相似结构的更小的图。这些合并图，每一个都有不同的粒度，提供我们原始图全局结构的视角。从最简单的形式开始，每一个图学习一系列初始表示，可以作为嵌入下一个更细节的图的良好初始。重复这个过程，直到我们得到原始图中每一个节点的嵌入。

Figure 6

属性网络嵌入

  在真实世界中，节点或边通常会关联额外的特征，称其为属性。例如在诸如 Twitter 的社交网络站点中，用户（节点）发布的文本内容是可用的。因此期望网络嵌入方法还从节点属性和边属性中的丰富内容中学习。这一部分仅讨论节点属性的工作。对不同类型的属性，有不同的策略。特别的，研究对两类属性感兴趣：高层次特征，比如文本和图片；和节点标签。

  挑战：高维稀疏特征，及如何将其整合到现有的网络嵌入方法。

  方法：

  • TADW

    • 研究节点与文本特征相关联情况

    • 第一次证明 DeepWalk 将转移概率矩阵 分解为两个低维矩阵，受此启发将文本特征矩阵合并到矩阵分解过程中。

  联合建模网络结构和节点特征（除了强制节点之间具有嵌入相似性，还应使具有相似特征向量的节点具有嵌入相似性）

  • CENE
    • 将文本内容视为特殊类型的节点，并利用节点-节点链接和节点内容链接进行节点嵌入。
    • 优化目标是共同最小化两种类型链路的损失。

  对于节点标签，整合标签信息的典型方法是联合优化产生节点嵌入和预测节点标签的损失。

  • GENE

异构网络嵌入

  异构网络具有多种类型的节点或边。大多数嵌入方法通过联合的最小化在每种模式上的损失来学习节点嵌入。这些方法或者在相同的隐空间直接学习所有节点的嵌入，或为每一种模式构造一种嵌入，然后将其映射到同一个隐空间。

网络嵌入的应用

  1. 知识表示。
    • 知识表示的问题是关于使用包含主语、谓语和对象的短句子编码关于世界的事实。
  2. 推荐系统。
    • 用户之间的交互，用户的查询和事项形成了一个异构网络，其编码了用户潜在的偏好。
  3. 自然语言处理。
    • 目前最先进的网络嵌入方法大多受自然语言处理领域的启发。反之，网络嵌入方法也可导致更好的建模人类语言。
  4. 社交网络分析。